﻿#include<iostream>
#include<vector>
#include<stack>
using namespace std;

//【题目】力扣739.每日温度
//【难度】中等
//【提交】https://leetcode.cn/problems/daily-temperatures/submissions/663423549/
//【标签】栈；数组；单调栈
class Solution 
{
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) 
    {
        int n = temperatures.size();
        stack<int>s;
        vector<int>res(n, 0);
        
        for (int i = 0; i < n; i++)
        {
            while (!s.empty() && temperatures[s.top()] < temperatures[i])
            {
                int index = s.top();
                res[index] = i - index;
                s.pop();
            }

            s.push(i);
        }
        return res;
    }
};

/*
学习总结：
通过维护一个单调递减栈（存储索引），当遇到比栈顶温度高的天数时，弹出栈顶并计算天数差，存入结果数组。
剩余未弹出的元素对应没有更高温度的日子，结果自动为0（初始化已处理）。
利用单调栈（递减）高效找到下一个更大元素的位置，避免暴力O(n²)搜索。
栈中存储索引而非值，便于计算天数差；遍历时比较当前温度与栈顶温度，触发弹出和结果更新
*/